perm filename DRAFT2[AP,DBL] blob
sn#123501 filedate 1974-10-08 generic text, type T, neo UTF8
00100 .DEVICE XGP
00200 .FONT 1 "FIX25"
00300 .FONT 2 "SIGN57"
00400 .FONT 3 "SHD40"
00500 .FONT 4 "BDI25"
00600 .FONT 5 "NGR20"
00700 .TURN ON "↓_π{"
00800 .TURN ON "⊗" FOR "%"
00900 .MACRO B ⊂ BEGIN VERBATIM GROUP ⊃
01000 .MACRO E ⊂ APART END ⊃
01100 .TABBREAK
01200 .COMPACT
01300 .SELECT 1
00100 .PORTION TITLEPAGE
00200 .BEGIN CENTER
00300 ⊗2AUTOMATIC SYNTHESIS OF
00400 LARGE INDUCTIVE
00500 INFERENCE PROGRAMS⊗*
00600
00700 ⊗4A Program-Understanding Program built around the concept of BEINGS⊗*
00800 .END
00900 .GROUP SKIP 10
01000 Second Draft
01100 .GROUP SKIP 10
01200 ⊗3DOUG LENAT
01300
01400 SAIL AUTOMATIC PROGRAMMING GROUP⊗*
01500
01600 .PORTION CONTENTS
01700 .GROUP SKIP 10
01800 ⊗2TABLE OF CONTENTS⊗*
01900 .GROUP SKIP 10
02000 .SELECT 1
02100 .B
02200 Abstract . . . . . . . . . . . . . . . . 1
02300 Introduction . . . . . . . . . . . . . . 2
02400 Ideas . . . . . . . . . . . . . . . . . . 3
02500 Design . . . . . . . . . . . . . . . . . 7
02600 Examples . . . . . . . . . . . . . . . . 11
02700 Performance . . . . . . . . . . . . . . . 15
02800 Conclusions . . . . . . . . . . . . . . . 19
02900 Acknowledgements . . . . . . . . . . . . 22
03000 Appendix 1: BEING parts . . . . . . . . . A1.1
03100 Appendix 2: the BEINGS . . . . . . . . . A2.1
03200 Appendix 3: BEING usage . . . . . . . . . A3.1
03300 Appendix 4: CF program . . . . . . . . . A4.1
03400 Appendix 5: the dialogue creating CF . . A5.1
03500 Appendix 6: trial running of CF . . . . . A6.1
03600 Bibliography . . . . . . . . . . . . . . BIB.1
03700 .E
03800 .SELECT 1
00100 .PORTION ABSTRACT
00200 .PAGE FRAME 53 HIGH 74 WIDE
00300 .EVERY HEADING(⊗4Synthesis of Large Programs⊗*,⊗3BEINGS⊗*,⊗4Doug Lenat⊗*)
00400 .EVERY FOOTING(⊗5Second Draft .... {DATE},page {IF PAGE = 1 THEN 1 ELSE PAGE})
00500 .COUNT PAGE PRINTING "1"
00600 .NEXT PAGE
00700 .GROUP SKIP 20
00800
00900 ⊗21. ABSTRACT⊗*
01000
01100 A system has been implemented which can synthesize large inductive
01200 inference programs from very restricted English dialogues. The
01300 technique is heuristic and knowledge-based, not formal. Both
01400 knowledge and control reside in highly structured pieces of code
01500 called BEINGS. Each BEING has a standard structure, and may
01600 therefore be viewed as an extension of the concept of ACTORS
01700 [Hewitt]. The output code of the system is also in the form of
01800 BEINGS. The synthesized program can answer questions about itself as
01900 it runs. A general description of the system which realized
02000 these ideas is provided, and its target domain is discussed. Some
02100 unexpected problems were encountered. Measures of performance of
02200 Automatic Programming Systems are proposed, and the current system is
02300 compared to previous ones. From all this emerges a "view" of future
02400 Automatic Programming work.
00100 .PORTION THESIS
00200 .GROUP SKIP 10
00300 ⊗22. INTRODUCTION⊗*
00400 This paper reports on a Program-Understanding Program (PUP6)
00500 capable of generating large LISP programs. The methods employed are
00600 not formal, but rather involve structuring of knowledge about
00700 programming, about the task domain, and about transfer of control. To
00800 date, PUP6 has synthesized three significantly different large
00900 (30-page) target programs: a concept formation program (similar to
01000 [Winston]), a grammatical inference program, and an information
01100 storage and retrieval system (referred to as, respectively, CF, GI,
01200 and AIR). Specification is via extended dialogues carried on with the
01300 user, in a small subset of English, in which the task is delineated
01400 and questionable details are discussed. The specification is
01500 partial, and the system makes assumptions continually.
01600 During the course of this research, a new representation for
01700 knowledge, BEINGS, evolved. They combine some of the advantages of
01800 uniformity and of structure, needed for intelligent action. PUP6 only
01900 uses this concept for automatic program synthesis, but its success
02000 indicates that the BEINGS representation has some merit. In order to
02100 decide how successful PUP6 was, it was necessary to develop standards
02200 to judge automatic programming systems; these will be presented in
02300 section 6.
02400 Our treatment will follow these lines: First, the ideas are
02500 presented, including a discussion of BEINGS. The next section
02600 describes the implementation, and explains the choice of targets.
02700 Only then will performance be evaluated. From the experience with
02800 PUP6 are drawn several preliminary conclusions about the future of
02900 Automatic Programming.
03000 The appendices present further details, samples, and examples.
03100 First comes a description of each BEING part, then a summary of the
03200 knowledge contained in each BEING. Appendix 3 is a table of data
03300 recording how the BEING community interacts. The final appendices
03400 present excerpts from the CF program, from PUP6 synthesizing CF, and
03500 from CF itself running.
00100 .NEXT PAGE
00200 ⊗23. IDEAS⊗*
00300 How should knowledge be represented? Many researchers feel
00400 that a simple, uniform formalism should be used for all facts; others
00500 disagree, claiming that complexity of behavior both justifies and
00600 demands complexity of representation. The BEINGS concept may resolve
00700 this uniformity vs. structure controversy; at the least, it is a
00800 compromise. One must recognize the advantages of each side, and
00900 refuse to give them up. The benefits of the former include easy
01000 addition of knowledge [Newell] and simple, aesthetic methods for
01100 combining information [McCarthy]. Structure, however, is necessary
01200 for (⊗4combinatorially⊗*) efficient handling of large amounts of data
01300 (see the real world; also [MIT]). PUP6 integrates these two ideas
01400 into the concept of BEINGS. A BEING is a collection of about thirty
01500 little bits of INTERLISP [Teitelman] code; the answers to thirty
01600 questions about the BEING. That is, a small program is considered
01700 equivalent to its answers to these fixed questions. Every scrap of
01800 knowledge, every bit of control structure should be encoded into
01900 BEINGS. There should be nothing else in the system but this
02000 interacting community. In the actual implementation, economy
02100 demanded some very fast auxilliary functions and some pure data
02200 structures. These reduced the computation time by a constant factor
02300 (about ten), by saving on the overhead implicit in each call to a
02400 BEING; they did not therefore reduce the ⊗4combinatorial⊗* effort
02500 involved.
02600 Notice that while each BEING is highly structured, this
02700 structure is standard over the entire pool. Each BEING part is itself
02800 a little BEING, etc., and this infinite regress stops when the
02900 contents of a BEING part becomes sufficiently primitive. As will be
03000 discussed later, the BEINGS mimic a human programmer; whatever he
03100 considers primitive when writing the program, PUP6 may consider
03200 primitive. Typically this level is about the same as the INTERLISP
03300 [Teitelman] language: a primitive is a single INTERLISP function
03400 call, or a few simple ones connected trivially. Each BEING is
03500 cognizant of the set of thirty questions, and in answering one of
03600 them it may freely ask questions of other BEINGS (often through
03700 nondeterministic goal statements.) A few of the BEING-PARTS might be:
03800 what is your basic idea and purpose, what effects do you have, how do
03900 you go about causing them, what must be ensured before you begin, how
04000 complicated are you, what is your chance of success, are you
04100 recursive, who else might you transfer control to, what alternatives
04200 to you exist, what BEINGS are a little more/less general than you
04300 are, do you evaluate your arguments, what is the nature of the value
04400 you return, why do you exist, why do you want to be in control now,
04500 etc. The reader may wish to glance at Appendix 1, to see the
04600 particular set of questions which were actually settled upon. When
04700 he feels the urge for a concrete example, he should glance over pages
04800 11, 12, and Appendices 4 and 5.
04900 BEINGS are the only entities permitted (theoretically) to
05000 exist in our system; ergo all our code must be written as BEINGS, and
05100 must be written by BEINGS.
05200 A crucial consequence is that ⊗4some⊗* BEINGS must write new
05300 BEINGS. A new idea is that the BEING who knows about ⊗4X⊗* takes
05400 charge of generating BEINGS relating to ⊗4X⊗*. For example, the
05500 SEARCH BEING can do searching, and he can also write specialized
05600 search routines, and he can answer questions about searching. This
05700 idea is analogous to any reliance upon experts (e.g., [Feigenbaum]),
05800 which is the theme of any modular representation of knowledge.
05900 A second consequence is that the output code will have all
06000 the "intelligence" that any BEING community has: it can write
06100 variations of itself, modify itself according to the user's
06200 complaints, and answer questions about what it is doing as it runs.
06300 In a similar vein, ⊗4some⊗* BEING(s) must do the translation
06400 of the users' quasi-English inputs into BEING-usable form. ↓_Each_↓
06500 BEING ⊗4X⊗* recognizes English related to ⊗4X⊗*. Thus translation
06600 consists of querying "who can recognize ..." and waiting for a
06700 response. For example, our SEARCH BEING must also recognize and
06800 process phrases involving searching or ordering.
06900 Three of the ideas present are constraints which reflect the
07000 author's philosophy: one need not feel any reverence toward the
07100 anthropomorphic paradigm of programming (ignore details, catch them
07200 by blind debugging.) As in all programming, decisions continually
07300 crop up which the system is not able to resolve at the time. PUP6
07400 will always spend a significant effort deferring the decision as long
07500 as possible. When, at last, no progress can be made without its
07600 resolution, and if the system is still unsure, then either the user
07700 settles the question or else a backtrack point is reluctantly set up.
07800 But often, by this time, some new information is present which
07900 enables PUP6 to resolve the decision, thus reducing the amount of
08000 backtracking. If there are two or more decisions which can no longer
08100 be deferred, the system tackles first the one estimated to be the
08200 easiest [Dijkstra].
08300 The final bit of philosophy is that most of the carelessness
08400 bugs can be eliminated through this deferral, feed-forward, and very
08500 precise record-keeping. Humans depend on their adaptability to
08600 compensate for limitations in their brain hardware (long write times
08700 for long-term memory and external memory, and limited short-term
08800 memory size force us to ignore details; see [Newell]) but there is no
08900 need for an ⊗4automatic⊗* programming system to do so. For example,
09000 when a list structure is first encountered, the system records
09100 warnings that it is undefined, no accesses, insertions, or deletions
09200 have been observed, and so on. Each such worry is weighted, and
09300 periodically PUP6 resolves such warning notes -- especially near the
09400 completion of the target program.
09500 The BEINGS concept is oriented toward simulating any complex
09600 task ⊗4T⊗* involving frequent small interventions by various experts.
09700 In addition to writing programs, this activity could be as diverse as
09800 playing chess, running a business, simulating physical interactions,
09900 and playing volleyball. For the latter task, PUP6 would create a
10000 specialized BEING for each player, perhaps with a complexity vector
10100 indicating his abilities, reflexes, etc. The BEING in control would
10200 be the player hitting the ball. A specialized Choose-from BEING
10300 would decide who goes next, occasionally interpreting a tie between
10400 BEINGS vying for control as a collision on the court.
10500 There is one particular bias of BEINGS toward writing
10600 high-level programs, over other activities. The new BEINGS created
10700 during the execution of a specified task are kept distinct from the
10800 original set of BEINGS. Then a ⊗4program⊗* for task ⊗4T⊗* is
10900 accomplished by doing ⊗4T⊗* and then dumping the new BEINGS out onto
11000 a new file. All of PUP6 is then treated as the language supporting
11100 this file. As a corollary, asking PUP6 to write any subset of
11200 itself is the null task!
11300 Perhaps this is merely an instance of a general "Hypothesis
11400 of Rationality" of intelligent Automatic Programming (AP) systems:
11500 Let α be an inductive inference program which is also an automatic
11600 programming system. If α understands programming, can introspect,
11700 approves of itself, writes inductive inference program β, could have
11800 read and understood and approved of β, then most of β may be similar
11900 to some subset of α. (Plausibility: otherwise, α would want to alter
12000 itself).
12100 Most programmers intentionally augment their code to aid in
12200 later debugging, modification, and readability by humans. These aids
12300 are typically comments, summaries, over-generalized subroutines,
12400 optional print statements, and runtime statistics. Recently, the
12500 structure of the program itself has been recognized as a powerful
12600 manipulable element. The length of a program written by PUP6 as
12700 BEINGS is several times as long as a hand-coded version. This extra
12800 code, the parts of each BEING in β which are superfluous, may be
12900 viewed as well-organized self-documentation! They should -- and do
13000 -- improve the debugging, expansion, and accessibility (to alien
13100 users) of the synthesized code.
13200 When imagining an ideal AP system, one ability we might wish
13300 for is that it be able to input a well-documented program and glean
13400 pure programming knowledge from it, and transform this into a format
13500 it can use. Also, to improve itself, it should be capable of
13600 digesting a sample, valid AP dialog, and (perhaps through additional
13700 user interaction) modify itself so it could actually carry on that
13800 dialog. PUP6 cannot meet these ideals; the BEINGS idea is probably an
13900 insufficient framework for achieving them. But PUP6 has turned out
14000 to be a satisfactory experimental vehicle: by studying its
14100 difficulties, isolating those due to poor implementation from those
14200 due to poor ideas, enough may be learned to build the next system one
14300 step closer to this ideal.
14400 It is in this spirit that BEINGS are now contrasted against
14500 the concepts of ACTORS, FRAMES, formal AP systems, and macro
14600 expansion schemes.
14700 ACTORS [Hewitt] provided the key concept of integrating
14800 uniformity of construction with sophistocation of behavior. There
14900 are, however, many things one wants to know about a routine, other
15000 than its value and its control successor. The structure isn't rich
15100 enough to allow ACTORS to communicate in a ⊗4descriptive⊗* way.
15200 FRAMES [Minsky] seems superficially similar to BEINGS, but
15300 there is a deep difference: FRAMES intentionally suggest that default
15400 values be filled in immediately, and replaced only when necessary.
15500 This is akin to automatic programming by blind debugging, but is
15600 antithetical to the fastidious bookkeeping BEINGS philosophy.
15700 The formal manipulation systems which also synthesize code
15800 are so different from BEINGS, that it is difficult to compare them.
15900 These logical systems (e.g., [Luckham]) attack an entirely different
16000 problem. Their task is specified rigorously in advance, and they
16100 proceed formally to search for a solution program. PUP6 works on a
16200 much higher level, heuristically. Each action is implicitly
16300 justified by the fact that the user can later describe to PUP6 what
16400 is wrong with the program it's generated. BEINGS can thus
16500 (theoretically) tolerate user ambiguity and error.
16600 Like ⊗4any⊗* AP system which writes structured programs, the
16700 external behavior of PUP6 is reminiscent of macro expansion
16800 regardless of ⊗4what⊗* the internal BEING interactions are! One
16900 major distinction between the two concepts is ⊗4when⊗* the "macros"
17000 are inserted: PUP6 has them inside all the time, as its knowledge
17100 base; a macro expander would demand each one from the user, just
17200 prior to and/or during the synthesis. Traditionally, macro
17300 expansion has been a very rigorous, syntactic process. Although this
17400 is changing toward increasing decision-making power, the connotations
17500 of context-free grinding remain. It would thus be misleading ⊗4at
17600 present⊗* to refer to PUP6 as merely a smart macro-expander.
00100 .NEXT PAGE
00200 ⊗24. DESIGN⊗*
00300 A highly polished presentation of a large system omits
00400 mention of the design and implementation mistakes. This is
00500 unfortunate; many decisions which seem arbitrary are the result of
00600 painful re-working, and conversely. The reader may relax; he will
00700 find nothing polished about this treatment!
00800
00900 Considerable attention was spent on choosing an appropriate
01000 domain of target programs. The choice, inductive inference (II),
01100 [Kant] merits discussion. The obvious difficulty appears to be the
01200 complexity of the programs involved: they are two orders of
01300 magnitude larger than any previously synthesized programs. But
01400 there are four big attractions:{BREAK} (i) A wide range of complexity
01500 exists, from a one-page sequence extrapolator to Meta-Dendral.{BREAK}
01600 (ii) Each increasingly sophisticated II program uses many of the
01700 concepts embodied in simpler II programs.{BREAK} (iii) If a
01800 super-human target program is ever written, it could itself
01900 contribute to the field of Automatic Programming! (For those reading
02000 this in the 1970's, this is humorous. For those later readers, it may
02100 be tedious.) {BREAK} (iv) Since we who write AI (and especially AP)
02200 programs are the "experts" on inductive inference ourselves, our
02300 reliance on introspection is as valid -- and potentially as valuable
02400 -- as chemists' protocols were to Dendral.
02500
02600 After studying many sample programs from the II domain, sequence
02700 extrapolation [Pilvar] seemed the most reasonable beginning task. It
02800 was quickly learned that this was too easy: humans have only a few
02900 techniques for extrapolating sequences, and a very limited capacity
03000 for composing them. Thus a rather rigid sequence extrapolator
03100 writer may be capable of generating a large class of super-human
03200 programs (see section *.* on Sequence-Extrapolator-Writer, by the
03300 author, in [Green]).
03400 The next candidates were grammatical inference and concept
03500 formation. Determined not to choose too simple a task again, the
03600 latter program was finally decided upon. The particular target was a
03700 variant of [Winston]. Any AP system should naturally possess much
03800 more domain-specific knowledge than is strictly necessary to write
03900 that one program! To make the goal more tractable, certain parts of
04000 Winston's description were ignored, namely the heuristic
04100 graph-matching section, and the uniformity requirement that relations
04200 on features be functionally indistinguishable from features.
04300 It seems instructive now to describe how the target program
04400 should operate. It repeatedly scans a scene and tries to name it. The
04500 scene is broken into a set of features, each of which is a relation
04600 on one or more objects in the scene. Internally, the program
04700 maintains a model for each distinct concept it has been told about.
04800 The model contains a description of the objects expected in the
04900 scene, a set of features which must be present in the scene (else it
05000 can't be the same as this concept), a set of features which must not
05100 be present in the scene, and a set of features which may or may not
05200 be present. Thus a model is like an archtypical scene plus a name.
05300 Each time the program is confronted by a new scene, the program must
05400 scan its models until it finds one which matches it. That is, all the
05500 model's MUST features are present, and all the MUSTNOT features are
05600 absent from the observed scene. It informs the user of this guess,
05700 and accepts the proper concept name. If it guessed incorrectly, it
05800 modifies its models. The wrong guess model may have features added to
05900 its MUST or MUSTNOT sets; the correct concept name model may have to
06000 be modified or (if it's a new concept) created and inserted into the
06100 list of models.
06200 .B
06300
06400 For example, a scene might be: OBJECTS a,b,c,d
06500 (GREEN a)(BLUE c)(TOUCHING c d)(SUPPORTS a c)(SUPPORTS b c).
06600
06700 A model for an arch might be: OBJECTS a,b,c
06800 MUST (SUPPORTS a c)(SUPPORTS b c)
06900 MUSTNOT (TOUCHES a b)
07000 MAY (GREEN a)(WEDGE c)(PRISM a)(BLOCK b)(PARALLEL a b)
07100 .E
07200 Suppose that the target program reads in the above scene and
07300 tries to match it to the above model for consistency. The MUST
07400 relations should all be present. Yes, the scene does contain
07500 (SUPPORTS a c) and (SUPPORTS b c). Next, the MUSTNOT relations must
07600 be absent from the scene. Sure enough, (TOUCHES a b) isn't there. So
07700 the model and scene are consistent. If the user verifies this guess,
07800 then the MAY list is augmented with (BLUE c) and (TOUCHING c d), and
07900 the OBJECTS list is augmented with "d."
08000
08100 After the target concept formation program was specified, it
08200 was trimmed and then rewritten as a structured program [Gadwa]. Next,
08300 a complete dialogue was simulated between the user and a human
08400 programmer playing the role of an "intelligent" automatic programming
08500 system (similar to, e.g., [Balzer]). The dialogue was then
08600 annotated: after each user response, comments were inserted which
08700 described the "states" the system-player had gone through before
08800 printing his next response. This included blind paths which were
08900 tried, use of outside world knowledge, and, in general, was meant to
09000 be the "intelligence" necessary to do the task. Our fear was that a
09100 system could be built which synthesized the concept formation
09200 program, and yet was so unintelligent that we learned nothing from it
09300 (see section *.* on PW1, for example, in [Green]). Hopefully, any
09400 system which (i) got the target program correctly, (ii) followed our
09500 initial dialogue, and, most importantly, (iii) went through the same
09600 line of reasoning that our comments indicated the human followed,
09700 would be far along the road toward intelligence. A corollary of
09800 this incremental annotated protocol approach is that the abilities of
09900 the user must coincide with those of the subject who participated in
10000 the protocol (see also [Woods]). So our target user is familiar with
10100 LISP, well-grounded in computer science, and has the concept
10200 formation (CF) task very clearly in his mind. The natural language
10300 front end is so brittle that the user must also phrase his responses
10400 very similarly to those of the original subject.
10500 At this point, most of the ideas described in the preceding
10600 section surfaced, including a rough initial set of BEINGS. Each one
10700 had not much more than a name and a vague description of what it must
10800 do. The dialogue was cycled through again, painstakingly, and the
10900 comments were replaced by a description of which BEINGS would call
11000 which other BEINGS, why, and the results of each such call. The
11100 constraints on each BEING thus grew, sometimes changed, and
11200 occasionally a new BEING or BEING part had to be added to the
11300 community. This process was long (200 hours) and produced a long
11400 (200-page) protocol, actually a hand trace of the system execution.
11500 About eighty BEINGS were needed, a dozen of which we viewed as
11600 domain-specific and the rest of which were domain-independent
11700 programming knowledge. About thirty different BEING parts were
11800 called for, and they are listed in Appendix 1. The next appendix
11900 describes each BEING briefly; only the most important knowledge is
12000 mentioned.
12100 A result of this method of incremental specification of
12200 BEINGS is that each BEING has only those parts which are going to be
12300 used sometime during the ensuing dialogue. This seemed too specific,
12400 so some effort was spent filling out parts that weren't strictly
12500 necessary to write the concept formation program. During the course
12600 of massaging PUP6 into writing the other target programs, very few
12700 additional parts had to be added to existing BEINGS. Typically,
12800 either an old part had to be generalized or else a new BEING created.
12900 After writing CF, GI, and AIR, there are now an even hundred BEINGS
13000 in PUP6.
13100 The data on how filled out each BEING was -- and had to be --
13200 is presented in several forms, here and in the appendices. In
13300 Appendix 1, next to each BEING part is the percentage of BEINGS which
13400 had to have this part specified for them. Appendix 3 reveals how
13500 each BEING was actually used, including the number of its BEING parts
13600 which exist and were called upon during a dialogue. On the average,
13700 each BEING part was present in 36% of all BEINGS, and, also on the
13800 average, each BEING had 10.5 of its 29 parts specified.
13900 The principle that "everything is BEINGS" was relaxed in the
14000 interests of absolute CPU time and feasibility of coding. Besides
14100 BEINGS, PUP6 employs functions, demons and an assertional data base.
14200 During the programming, 100 small functions were written to
14300 supplement the language. Most were typical current AI language
14400 features [Bobrow] (pattern-matching, demons, special data types), or
14500 tiny additions to INTERLISP [Teitelman] (flatten, set-difference), or
14600 functions which manage BEINGS (add-a-new-being,
14700 print-a-being's-parts). Many of these features were simplified (and
14800 speeded up) by using the knowledge that PUP6 was to be an AP system.
14900 For example, all the different types of assertions that an AP system
15000 might want to make deal with different concerns of programming. Thus
15100 a group of about forty different assertion patterns could be fixed,
15200 each one becoming a named list; this almost eliminated searching
15300 during retrieval from the assertional base.
15400 The initial programming took only a hundred hours, but
15500 several times that amount of work was required before the system was
15600 debugged to the point of successfully following the annotated
15700 dialogue.
00100 .NEXT PAGE
00200 ⊗25. EXAMPLES⊗*
00300 This section presents examples of the following: a
00400 programming knowledge BEING, an explanation of what happens when a
00500 BEING is called, a concept formation knowledge BEING, and
00600 descriptions of two piece of the user-PUP6 dialogue.
00700 5.1. OBTAIN_USABLE_INFORMATION is a typical high-level,
00800 domain-independent BEING. The WHEN part is a perceptron whose
00900 feelers sample the world and report their qualities numerically. This
01000 is bad; one would like them to discuss descriptions of what they
01100 encounter; but the WHEN part is used only to break ties between
01200 BEINGS vying for control, and it usually doesn't matter what order
01300 they go in. Thus a simple, fast method of selection is adequate.
01400 This particular BEING has feelers which respond that it is ⊗4always⊗*
01500 an undesirable (-10) thing to do, but ⊗4may⊗* be indicated (+111) if
01600 there exists new but not yet usable information. The META-CODE has
01700 us choose from the following four alternatives, each of which is
01800 itself a BEING: Get_Brand_New_Information (in English, from the
01900 user), Translate (transform from English to BEING-calls) something,
02000 Analyze_The_Implications (of some existing, translated information),
02100 Extract_a_Relevant_Subset (of the existing information) to
02200 concentrate upon.
02300 Below are exhibited the actual representation of this BEING
02400 in PUP6, and the function which would be executed if it were
02500 ⊗4called⊗*.
02600
02700 .SELECT 5
02800 .BEGIN NOFILL
02900
03000 (PUTPROPS OBTAIN:USABLE:INFORMATION
03100 IDEN (((AND (EQUAL (CAR LI)
03200 OBTAIN:USABLE:INFORMATION)
03300 (EQUAL (LENGTH LI)
03400 2))
03500 (OBTAIN:USABLE:INFORMATION (TRANSLATE (CADR LI))))
03600 BEING T
03700 EXPLICIT:ARGS (U)
03800 WHAT (TUPLE OBTAIN SOME INFORMATION WHICH CAN BE USED)
03900 HOW (TUPLE OBTAIN NEW FACTS ABOUT OLD INFORMATION, OR OBTAIN TOTALLY
04000 NEW INFORMATION)
04100 WHY (TUPLE PUP HAS NO MORE INFORMATION THAT IT CAN USE TO PROGRESS)
04200 WHEN ((T -10 (TUPLE SINCE THIS IS AN EXPONENTIALLY-GROWING, BAD THING
04300 TO DO IN GENERAL))
04400 (NEW:INFO:LIST 111
04500 (QUOTE (BECAUSE WE SHOULD WORK ON UNASSIMILATED NEW
04600 INFORMATION IF THERE IS ANY))))
04700 META:CODE (PROGN (SETQ BECAUSE
04800 (QUOTE (WE CAN ONLY TRY TO OBTAIN USABLE
04900 INFORMATION IN ONE WAY AT A TIME)))
05000 (CHOOSE:FROM (QUOTE ((TRANSLATE U)
05100 (GET:NEW:INFORMATION U)
05200 (ANALYZE:IMPLICATIONS U)
05300 (EXTRACT:RELEVANT:SUBSET U)))))
05400 EXPLICIT:ARGS:CHECK T
05500 MAIN:EFFECTS (((NEW INFO ANY1)
05600 (OBTAIN:USABLE:INFORMATION (@ ANY1)))
05700 ((USABLE INFO ANY1)
05800 (OBTAIN:USABLE:INFORMATION (@ ANY1))))
05900 AFFECTS (QUOTE ((CHOOSE:FROM CALLED)
06000 (TRANSLATE POSSIBLE:CALLED)
06100 (GET:NEW:INFORMATION POSSIBLE:CALLED)
06200 (ANALYZE:IMPLICATIONS POSSIBLE:CALLED)
06300 (EXTRACT:RELEVANT:SUBSET POSSIBLE:CALLED)))
06400 COMPLEXITY:(.5 .5 .5 .5 .1) )
06500
06600 ⊗15.2. When a BEING is ⊗4called⊗*, its parts are assembled
06700 into a function which is then executed. Here is the ⊗4FUNCTIONAL⊗*
06800 form of the above BEING:⊗*
06900
07000 (OBTAIN:USABLE:INFORMATION
07100 (LAMBDA (U FN:VALUE FINAL:CO:REQ)
07200 (PROG1
07300 (AND
07400 (SETQ BEING:STACK (CONS OBTAIN:USABLE:INFORMATION BEING:STACK))
07500 (PUT OBTAIN:USABLE:INFORMATION SPEC:WHY BECAUSE)
07600 (EVERY (APPEND CURRENT:DEMONS USER:INTERRUPT:DEMONS)
07700 (QUOTE APPLY*))
07800 (SETQ BECAUSE
07900 (QUOTE (WE CAN ONLY TRY TO OBTAIN USABLE
08000 INFORMATION IN ONE WAY AT A TIME)))
08100 (CHOOSE:FROM (QUOTE ((TRANSLATE U)
08200 (GET:NEW:INFORMATION U)
08300 (ANALYZE:IMPLICATIONS U)
08400 (EXTRACT:RELEVANT:SUBSET U)))))
08500 (SETQ BEING:STACK (CDR BEING:STACK)))))
08600 .END
08700 .SELECT 1
08800
08900 The process of assembling the BEING parts into a function is
09000 straight-forward. First, the explicit arguments (those global to the
09100 BEING) are bound. The implicit arguments (those local to the BEING,
09200 like PROG variables) are initialized. The name of the BEING is pushed
09300 onto the BEING control stack (pointing to its caller), and any
09400 newly-activated demons are pushed onto the demon staack. The
09500 ARGS-CHECK predicates are evaluated. Then PUP6 works to make each
09600 PRE-REQUISITE true in the world. Each COMMENT is evaluated, then the
09700 CO-REQUISITES, META-CODE, and current demons all are executed in
09800 pseudo-parallel. Each POST-REQUISITE is then satisfied. Any of these
09900 activities could report failure, and the entire BEING would then halt
10000 and return failure. In both cases, just before exiting, the demon
10100 stack is popped and the BEING stack is updated (usually just popped),
10200 and control passes to the delegated BEING (usually the one who called
10300 this BEING, at the state when he called it.) A fancy context
10400 mechanism was available but not actually needed.
10500 This seems a reasonable place to describe how the BEING parts
10600 not used in assembling the functional form ⊗4are⊗* used. The IDEN
10700 parts are collected together into a large translation table. When a
10800 form ⊗4LI⊗* must be translated, the TRANSLATE BEING goes through this
10900 table, asking each IDEN part if it claims to recognize ⊗4LI⊗*. Each
11000 IDEN runs its own little program, typically some type of pattern
11100 match involving ⊗4LI⊗* and the state of the world, to answer this
11200 question. Some measure of goodness of match is also reported. If
11300 there is more than one responder, CHOOSE-FROM picks the one with the
11400 highest priority of match. The winner runs a little program which
11500 ultimately returns a BEING-call or a constant as the translated value
11600 of ⊗4LI⊗*. This program might call other BEINGs, often calls
11700 TRANSLATE several times recursively on parts of ⊗4LI⊗* (see the IDEN
11800 part of the above BEING, for example. If two conditions are met, it
11900 says to ⊗4call⊗* OBTAIN-USABLE-INFORMATION with, as argument, the
12000 result of calling TRANSLATE on the second element of ⊗4LI⊗*.)
12100 The EFFECTS parts of each BEING are similarly collected into
12200 one table to facilitate asking all BEINGs simultaneously "Can you
12300 cause X to occur?" Each EFFECTS part examines X and the world, and
12400 either replies No, or else returns a little program (involving calls
12500 and constants) which should produce the effect, with a certain
12600 probability. This program will probably involve a call to the BEING
12700 itself.
12800 The WHAT, HOW, and WHY parts are mainly for the user's
12900 benefit. When a choice between BEINGs must be made, the WHEN,
13000 AFFECTS, and COMPLEXITY-VECTOR parts are queried. If a new,
13100 manipulated version of the BEING must be created, the
13200 SPECIALIZATIONS, ENCODABLE, DATA-STRUCTURE, PREDICATE, and
13300 FORM-CHANGING parts might be relevant. If the BEING fails, some
13400 ALTERNATIVE BEING might be tried; if that also fails, some
13500 GENERALIZATION BEING could be called.
13600 5.3. To PARTITION_A_DOMAIN in an inductive manner, one must
13700 make a few choices. The partition may be only partial (an element of
13800 the domain belonging to no equivalence class), it may be only weak
13900 (an element may belong to more than one class), and, most
14000 importantly, the BEING should partition by doing only some of these 3
14100 acts: accept a class-name and get some of its elements, accept an
14200 element and get its class-name, accept <element, class-name> pairs.
14300 Other BEINGS know about each of these alternatives. During the
14400 partitioning, the only new demon to keep active is the one called
14500 Fringe_of_Consciousness.
14600 5.4. The dialogue begins by PUP6 asking the user for any
14700 task. The user replies, "Write a program which does concept
14800 formation." There are many decisions that PUP6 knows about in writing
14900 a specialized concept formation program, and it manages to defer them
15000 all. For example, it must choose between classificatory,
15100 comparative, and metrical concept formation. Since all three involve
15200 partitioning a domain of examples, PUP6 decides it can defer this
15300 choice until after code for the partitioning is synthesized. Hours
15400 later, the system asks the user to make this decision, he picks the
15500 first alternative, which involves only partitioning, and the system
15600 prints that it has finished the task!
15700 5.5. Let's now jump ahead, one third of the way into the
15800 dialogue. The system learns it must compare the input scene against
15900 its internally stored models of concepts, until it finds one which
16000 doesn't fail the comparison. It asks the user what it means for
16100 scene S to fail the comparison to model M. The user replies, "M is
16200 incompatible with the observed features of S." The IDEN part of the
16300 CONTRADICTS BEING recognizes this sentence pattern, and transforms it
16400 to (FORSOME F IN M_FEATURES (CONTRADICTS F S_FEATURES)). The BEING
16500 which inserts this into the synthesized code requires that the user
16600 pick some proper name for the function CONTRADICTS; say the user
16700 types in #. The function FORSOME is so primitive that no
16800 specialized version of it is written normally. The system informs
16900 the user of where it is by means of a cursor pointing into a graph of
17000 program code. This is analogous to the textual and dynamic indices
17100 which [Dijkstra] suggests. Later in the dialogue, PUP6 decides it
17200 must expand the function #. The CONTRADICTS BEING is again called on;
17300 this time it is asked how to write a specialized version of a
17400 contradiction test. It replies that SOME_OF the following types of
17500 contradiction may occur: PROBABILITY:0, PROBABILITY:1, and
17600 PROBABILITY:ε(0,1). This is the germ of the idea for the
17700 MUST/MUSTNOT/MAY categorization of features. The SOME_OF BEING takes
17800 control, and asks if the decision can be deferred. The DEFERRAL
17900 BEING looks about, first asking if there is any non-null piece of
18000 code that all three have in common. This fails, and eventually the
18100 DEFERRAL BEING reports failure. SOME_OF sees it has no basis upon
18200 which to form a guess, and wants somebody to ask the user. The
18300 ASK_USER BEING takes over, and quickly finds out what it is that PUP6
18400 wants to learn. The names of the three choices are so cryptic that
18500 their WHAT and HOW parts are printed out to the user, as well as
18600 their names. The user types back his choices, in our case all three.
18700 SOME_OF composes three new function calls, separated by a
18800 conditional:
18900 .B
19000
19100 (COND ( (IS_OF_TYPE F PROBABILITY:0_PART_OF_M_FEATURES)
19200 (PROBABILITY:0_# F S_FEATURES))
19300 ( (IS_OF_TYPE F PROBABILITY:1_PART_OF_M_FEATURES)
19400 (PROBABILITY:1_# F S_FEATURES))
19500 ( (IS_OF_TYPE F PROBABILITYε(0,1)_PART_OF_M_FEATURES)
19600 (PROBABILITYε(0,1)_# F S_FEATURES)))
19700 .E
19800 A trichotomy demon recognizes this as a split on a function's values
19900 being =0, =1, or between zero and one. It asks whether this
20000 particaular function can only range over the interval [0,1].
20100 PROBABILITY answers affirmatively, so SOME_OF replaces the final
20200 IS_OF_TYPE test by the constant T. Later on, PUP6 must worry about
20300 the other two tests, and about the three contradiction predicates.
20400 These latter entities know (their ENCODABLE parts tell them) that
20500 they are immediately encodable. A probability=0 contradiction means
20600 that arg1 must not occur in the world arg2 yet it does. So it is
20700 defined as (MEMBER arg1 arg2). This corresponds to a MUSTNOT
20800 feature F which is present in the world (in the set of S_FEATURES of
20900 the scene.) A probability=1 contradiction occurs when a feature arg1
21000 must occur in the world arg2, yet it doesn't. So its definition is
21100 simply (NOT (MEMBER arg1 arg2)). It is impossible for a feature
21200 with probability in (0,1) to be in contradiction with any world
21300 (lacking negated features), so this third predicate is defined as the
21400 constant NIL. That is, if F is a MAY feature of the model M, then
21500 there can be no contradiction between F and ⊗4any⊗* features of the
21600 scene S.
21700 The IS_OF_TYPE BEING recognizes that it must work hard to
21800 replace each of the two case tests, unless M_FEATURES is organized
21900 permanently into three parts (thus permitting the complex function
22000 "IS_OF_TYPE" to be replaced by the simple one "MEMBER" in the above
22100 piece of code). The STRUCTURE_INDUCING BEING will take over, to
22200 probe the permissability and the difficulty of such a constraint. It
22300 finds nothing about this tripartite structuring which could damage
22400 any earlier synthesized code, and asks the user's blessing. Notes
22500 are added to the list of coding warnings, stating that any reference
22600 to the entire list of M_FEATURES must be replaced by either APPEND of
22700 the three new lists, or else by three separate statements. GET_NAME
22800 is indirectly called, and he has the user name the three new sets of
22900 features; say he responds by calling them MUSTNOT, MUST, and MAY. The
23000 system would at this point draw an arrow on its graph of code, from
23100 the function call (# F S_FEATURES) to the new block of code:
23200 .B
23300
23400 (COND ( (MEMBER F MUSTNOT_LIST_OF_M)
23500 (MEMBER F S_FEATURES))
23600 ( (MEMBER F MUST_PART_OF_M)
23700 (NOT (MEMBER F S_FEATURES))
23800 ( T (COMMENT THIS "T" REPLACES "MEMBER F MAY_PART_OF_M")
23900 NIL))
24000 .E
24100 Notice that only a few messages have passed back and forth during all
24200 this processing. The user has the feeling of merely directing,
24300 constraining, and watching the activities of a busy programmer. As
24400 was mentioned earlier, PUP6 insists on doing structured programming,
24500 so its traces are superficially similar to macro expansion. Despite
24600 its concentration on planning, PUP6 rarely believes it's finished if
24700 any details remain.
00100 .NEXT PAGE
00200 ⊗26. PERFORMANCE⊗*
00300 The character of the dialogue just decribed is, of course,
00400 one important measure of the intelligence of an AP system. One which
00500 asked "What is the first instruction? What is the second...?" would
00600 be universal but worse than useless. In this section are some
00700 proposed questions one should ask when confronted by a new AP system,
00800 some measures of performance of an AP system. These are applied to
00900 PUP6 and some earlier AP programs.
01000 The questions break into two categories. First, one wants to
01100 know what the system does. Most important, does it write a program?
01200 If so, how complex is that task, and what is the program
01300 specification like? How precise must the user be: may he err,
01400 forget, change his mind? How detailed must his dialogue be? How
01500 closely does the dialogue determine the details of the final code?
01600 How does the user know where he is during the dialogue?
01700 Quite seriously, an important question is whether the
01800 system writes a second program. If so, how does it relate to the
01900 first one synthesized? How much of the AP system is actually used
02000 in writing both programs? One should ask what the full range of
02100 programs is which the system has successfully synthesized. What
02200 about the target language: is it a parameter? how does it relate to
02300 the language the system is written in?
02400 Does the system modify as well as write code? If so, can
02500 it modify anybody's, or only those programs it has written itself?
02600 What is its "style" of programming? One also wishes to know the size
02700 of the tool as well as the size of the job: How does the system size
02800 compare to target program size?
02900 Regrettably, efficiency considerations are often the crucial
03000 pragmatic ones. Economics and current hardware restrict the amount of
03100 computation which may be done in toto; the expected lifetime of the
03200 universe restricts us from using the most elegant algorithms; and
03300 human patience restricts the interaction delay time (to a minute or
03400 so of real time -- [Winograd]). One must therefore ask things like
03500 how much time and space it requires, how long a delay there is
03600 between user inputs, etc.
03700 The second class of questions concerns the theoretical side
03800 of the AP system. What new ideas is it meant to experiment with? How
03900 do each of these ideas fare? Does it write its code in the right way
04000 (does it ask the right questions of the user at just the proper
04100 times)? How extendable is it: how difficult is it to add new pieces
04200 of knowledge and to modify old ones? Could it write programs in
04300 various fields, in various styles, in various sizes?
04400 How is knowledge represented internally? Is any of it
04500 duplicated? If so, what and why? Why doesn't this system solve the AP
04600 problem?
04700 PUP6's answers to most of the these questions are scattered
04800 throughout the earlier sections of this paper. Below are its answers
04900 to the remaining questions. Although BEINGS might have been designed
05000 to handle user errors, PUP6 was set up expecting that the user would
05100 never err or forget. He could, after the program was finished, try
05200 it out and describe how he wished it changed. For example, the
05300 data storage and retrieval system which was written was supposed to
05400 be a very simple airline resevation system. After the synthesis is
05500 finished, the user tries out the program and finds that he is unable
05600 to delete more than one reservation with any single command. He
05700 complains about this, and PUP6 modifies the program so that he may
05800 specify a pattern, and all reservations matching that pattern will be
05900 purged. While such assumptions of user reliability are reasonable
06000 for little programs, they break down when the tasks reach the size of
06100 tens of pages and hours.
06200 The table below shows how each type of knowledge was used in
06300 writing the three target programs. All numbers refer to BEINGS.
06400
06500 .BEGIN
06600 .GROUP
06700 .NOFILL
06800 .BREAK
06900
07000 .ONCE CENTER
07100 ⊗4U S E D I N S Y N T H E S I Z I N G⊗*
07200 TYPE OF CF CF CF CF GI AIR not Crea Crea Crea Total
07300 KNOWLEDGE GI GI AIR only only only used -ted -ted -ted BEINGS
07400 AIR only only ever in CF in GI in AIR
07500
07600 Programming 39 7 5 5 3 1 14 52 27 21 174
07700 Domain 0 3 0 9 8 1 5 4 10 3 43
07800 Total 39 10 5 14 11 2 19 56 37 24 217
07900 .END
08000
08100 The high percentage of programming BEINGS which were used in all
08200 three dialogues is exciting. The three domain-specific BEINGS used
08300 in both CF and GI sessions indicate that they may be Inductive
08400 Inference domain specific. They aren't used in AIR, which is not an
08500 inductive inference task. All three deal with partitioning a domain.
08600 A specialization of a general programming BEING is listed as
08700 a programming BEING still (in the CREATED columns of the above
08800 table.) This is because it remains sufficiently independent to be
08900 used in many ways, conceivably in many different programs.
09000 Let us briefly describe GI and AIR. GI is a simple
09100 grammatical inference program. It builds up a set a plausible rules,
09200 rather than enumerating through the space of all grammars. Yet it
09300 lacks most of the "tricks" of the best g.i. programs. The user
09400 repeatedly specifies a string, labelled LEGAL, ILLEGAL, or ??. In
09500 the latter case, GI must print out its guess and accept the correct
09600 label from the user. In all three cases, it must update its set of
09700 plausible rules to be at least consistent with all positive and
09800 negative instances observed. In some versions of GI written by PUP6,
09900 a parse tree may be maintained and inspected; in other versions, just
10000 a list of the rules used during a parse is kept.
10100 AIR is a data-retrieval-on-keys system, a very
10200 primitive type of an airline reservation system indeed! The user
10300 repeatedly types in a request to insert, delete, or inspect a record
10400 (e.g., INSERT: PASSENGER Jones FLIGHT 741 FROM SFO TO LAX CARRIER TWA
10500 LEAVE 7:15 ARRIVE 8:00). Any unspecified fields are treated as
10600 dont't cares; thus the request is matched against entries in the data
10700 base.
10800 The style of the synthesized programs is constrained since
10900 all code must be BEINGS. At a lower level, there are many trivial
11000 inefficiencies which are passed through an optimization BEING. It
11100 is vacuous now, but may soon contain a LISP optimizer being written
11200 by A. Cohn of the SAIL AP group. Low level efficiency was
11300 intentionally ignored to expedite work on PUP6. Nevertheless, the
11400 final code produced runs in about the same time as the hand-coded
11500 versions. It is several times as long, though, since it must be able
11600 to answer questions about what it's doing as it runs. The protocol
11700 version lacked this ability, of course.
11800 Ephemeral numerical efficiency data follows. PUP6 is 200
11900 pages long when PRETTY-PRINTED, and is aimed at programs which are
12000 one to 100 pages long. One crude measure of concentration of
12100 intelligence is to compare the system and target code lengths.
12200 A brute force AP system would require a time roughly
12300 exponential in target length, so log(time)/target_length (measured
12400 over several different programs and over several AP systems) is an
12500 indicator of the intelligence of an AP system. For a good system,
12600 this number should (i) be small absolutely, and, more importantly,
12700 (ii) decrease significantly as the target program length increases.
12800 For a ⊗4very⊗* good program writer, the quantity time/target_length
12900 stays almost constant. This is not quite achieved by human
13000 programmers known to the author.
13100 Below, the author compares PUP6 to two other of his AP
13200 systems, and to one ⊗4(NONEXISTENT!)⊗* system which would be advanced
13300 enough to "market" to AI programmers.
13400 .B
13500
13600 SYSTEM TARGET LENGTHS(lines) TIME(min) ln(time) DIALOG(chars)
13700 SYS. TARG RATIO /tar.size USER SYS
13800
13900 PW1(Brute) Merge 1000 5 200.0 3 .2 100 1000
14000 * CF 1000 2000 0.5 10**400 .2 500 2000
14100 PUP1(Rules) 3-sort 3000 30 100.0 15 .03 100 500
14200 PUP6(BEING) AIR 9000 600 15.0 8 .0035 800 10000
14300 GI 9000 1700 5.3 35 .0021 1500 30000
14400 CF 9000 2400 3.7 60 .0017 2500 50000
14500 Marketable* CF 50000 2400 20.1 30 .0014 500 2000
14600 * OS370 50000 100K 0.5 120 .00005 1000 5000
14700
14800 .E
14900 An asterisk above indicates that the numbers on that line are
15000 guesses. The dialogue lengths are best specified in characters,
15100 since often the user will supply simply a number or a letter or a
15200 YES/NO reply. Dividing these by a hundred, one can relate them to
15300 target and system lengths in lines. This was not done above,
15400 because the format of the AP dialogue can easily be varied by a
15500 couple orders of magnitude in almost every system! The mean wait
15600 time (between the user's input and the next machine output) is
15700 several seconds. The longest delay between successive user inputs
15800 is 1 CPU minute. Unfortunately, PUP6 requires 100K to run in, which
15900 (with INTERLISP) exhausts the virtual memory of the current hardware
16000 being used. One would lose vast amounts of time by using
16100 intermediate storage devices or by running consecutive communicating
16200 jobs.
16300 McCune calls attention to an argument against aiming at a
16400 system whose target programs will be longer and more complex than the
16500 system itself. First, empirically, optimizing compilers are viable
16600 and yet they dwarf almost all the code they generate. Second, as
16700 the complexity of the transformation increases, the length of a
16800 compiler increases rapidly. For a truly intelligent AP system, one
16900 might be willing to tolerate a program several times as large as
17000 anything it could produce.
17100 An argument exists to counter this one. First, one might
17200 object to drawing an analogy from compilers; many entities are
17300 capable of producing things more sophistocated than themselves,
17400 larger than themselves, etc. (look at evolution!) Second, it seems
17500 that there is a manageable body of information which one needs master
17600 to do programming [Informal]. Viewed differently [Dijkstra], one can
17700 write programs as long as he wishes if the program is designed in a
17800 clean way. Thus the size of the AP system will level off (albeit huge
17900 compared to existing programs) even as the size and complexity of its
18000 generated code continues to increase and, eventually, surpass it.
18100 Finally, we must consider why we want a good AP system: to help us
18200 write large programs easily, programs which might be unmanageable
18300 today. For this reason alone, our AP system must be able to deal
18400 with programs larger than itself.
00100 .NEXT PAGE
00200 ⊗27. CONCLUSIONS⊗*
00300 The remaining theoretical questions about PUP6 are treated,
00400 followed by a discussion of its strengths and weaknesses. This
00500 experiment has pointed out some of the important problems facing
00600 future AP work.
00700 Most of the theoretical questions are answered by the very
00800 design of the system. Its ideational foundation has been discussed.
00900 PUP6 asks the right questions at the right times because of its
01000 genesis from an annotated protocol. The second and third programs
01100 were attempted only to test its flexibility, and the results were
01200 mixed. The fact that target code is in the format of BEINGS limits
01300 the size of the target programs (≥ one page) and their efficiency (a
01400 BEING-call is a very slow and intricate process) and of course their
01500 style. The most startling result -- which should have been forseen
01600 -- was that "intelligent" target code is synthesized. This was
01700 mentioned casually in the IDEAS section, but its importance is clear:
01800 the code is self-commenting in the strong sense that the code can
01900 answer any (of our set of 29) questions about itself. Those which
02000 make sense at compile-time can be asked then; those which make sense
02100 during execution may be asked then. For example, CF begins running.
02200 After several scenes have been processed, CF is waiting for a new
02300 one. If the user interrupts and asks what it is doing, CF will reply
02400 "awaiting user input of a brand new scene." One can ask why, how, who
02500 will be affected, and so on, interrupt as frequently as desired --
02600 even after each BEING transfers control.
02700 The increment to PUP6 to enable it to write the GI and the
02800 AIR programs is encouragingly small: PUP6 may be converging on the
02900 core of simple LISP programming knowledge, perhaps on a sufficient
03000 system organization. Almost all the programming-knowledge BEINGS are
03100 called in writing more than one of the programs. It is now clear
03200 that very domain-specific BEINGS were in control at the early, high
03300 levels. Later, more general BEINGS took over, followed by pure
03400 programming BEINGS. The middle category would include II BEINGS
03500 like PARTITION_A_DOMAIN. PUP6 has taught us a few other interesting
03600 things. While the number of BEING-parts is unimportant, its
03700 magnitude (a few tens) may have significant consequences to AP. The
03800 fact that is isn't ~3 explains the difficulty that ACTORS and
03900 cyberneticists have; the fact that it isn't ~1000 means that the AP
04000 problem is tractible. Another tidbit in hindsight: the annotated
04100 protocol seems much more valuable now than during its tedious
04200 construction.
04300 Some of the ideas discussed at the beginning of the paper
04400 have proven themselves to be useful in getting PUP6 to work. Programs
04500 can indeed be treated as if their essence is nothing more than a
04600 collection of answers. The gain from standardization is easy
04700 addition of pieces to the system; one merely adds new BEINGS to the
04800 community. Indications are that one ⊗4can⊗* beat the combinatorial
04900 explosion (of locating relevant information) by organizing the
05000 knowledge in a pool, with each piece (i) responsible for recognizing
05100 when it is relevant and (ii) indicating new relevant information
05200 indirectly via nondeterministic pattern-directed retrievals and
05300 assertions. Notice that this puts all control structure into the
05400 hands of the BEINGS; there is no central monitor in PUP6. A BEING's
05500 answers may at various times indicate that it should be chosen to be
05600 in control, and it will then take over. Notice also that this
05700 relevancy problem is central to program maintenance as well as
05800 synthesis.
05900 The set of questions the user might want to ask the system is
06000 similar to the questions one BEING wants to ask another. So when the
06100 user interrupts, his questions are almost always a simple retrieval
06200 from a property list (a GETP or a composition like EVALπ.GETP).
06300 The careful bookkeeping actually did eliminate many
06400 carelessness errors, though it had no effect on user errors or later
06500 program maintenance directives. These latter processes are less
06600 ill-defined than blind debugging, and in fact are about the same as
06700 programming itself [Dijkstra]. The deferral of decisions has the
06800 nice corollary of reducing (though not minimizing) communication with
06900 the slow user channel, excessive use of which takes the ⊗4automatic⊗*
07000 out of automatic programming.
07100 A clean target program could probably successfully be
07200 attacked in many non-numerical domains, by adding a few domain-
07300 independent BEINGS and several domain-specific BEINGS. For example,
07400 to write the AIR program, only an EXAMINE_DATA_STRUCTURE BEING and a
07500 few new system functions (e.g., a better pattern-matcher)had to be
07600 added. The entire reprogramming effort took an hour. The session
07700 with PUP6 to get it to produce AIR took only thirty minutes of real
07800 time, which is less than it would have taken to write AIR by hand.
07900 Since the dialogues for GI and AIR were not studied before-hand,
08000 their acceptability would have demonstrated the success of the
08100 system. However, the dialogue to write AIR is too long and detailed
08200 for the task at hand. It also seems that the front end is too
08300 brittle to allow anyone unfamiliar with the system to easily work
08400 with it.
08500 The need for natural language flexibility stems only
08600 partially from inter-user differences. A serious and unexpected
08700 source of conflict here is the amount of inference the user wants
08800 done. This level is relatively subjective, and may fluctuate rapidly
08900 even with one user writing one program. Perhaps there should be a
09000 dial he can set; one extreme would be CAREFUL. The system would ask
09100 the user to verify even the most trivial inductions. The other
09200 extreme setting would be TRIAL. Here the system would probably write
09300 the target program after just a few brief user inputs. The user
09400 would then try out one program after another, interjecting just one
09500 or two comments each time, after which the system would come up with
09600 the next version. This program modification mode seems appropriate
09700 for someone ignorant of programming, who nevertheless has the I/O
09800 behavior of his target clearly in mind.
09900 Some of the BEING parts proved embarrassingly unnecessary.
10000 The CO-REQUISITES part was never used. The only activity which had
10100 to be done concurrently was demon activation. The AFFECTS part was of
10200 interest to the user occasionally, but never to any BEING! The
10300 EFFECTS part originally had a twin, describing what would happen if
10400 each BEING were ⊗4not⊗* called right now. In each case, this was
10500 merely a trivial restatement of the frame problem. So, like STRIPS
10600 [Fikes], PUP6 ignores the frame problem: all changes must be
10700 explicit.
10800 Much of PUP6's comments are boring and unnecessary; this was
10900 felt to be an engineering problem which would be ignored in all but a
11000 "marketable" AP system. This view was probably incorrect. One of the
11100 most severe AP problems is having the system inform the user of
11200 precisely what he should know -- no more nor less. This requires a
11300 sophisticated user model cleverly interfaced to the current
11400 programming task.
11500 Another problem with large, long dialogues is user error. A
11600 human has great difficulty keeping "on top" of everything. He may
11700 get lost, forget, change his mind, or misunderstand. Again, this
11800 problem was treated as a minor consideration, but has shown itself to
11900 be a limiting practical factor in wide accessability. It was
12000 necessary to create a forgetful-user demon to prevent anaphoric
12100 reference to something which, though uniquely determined, hadn't been
12200 mentioned in several hours! Related to this is the problem of keeping
12300 the user informed of where he is. PUP6 simulated a continuous display
12400 of the graph of the current partial program, augmented by static and
12500 dynamic cursors. This use of dynamic and textual indices seems
12600 insufficient. The user was still often confused, wishing a section
12700 referred to not by pointing but rather by a brief, meaningful (to him
12800 only!) phrase. This may also be one of the major AP problems which
12900 must be studied further.
13000 These worries about large dialogues arise because future AP
13100 systems are viewed as tools for writing programs which humans simply
13200 cannot manage currently: viable natural language systems, huge
13300 operating systems, better AP systems. The whole design of BEINGS is
13400 oriented toward this large-scale end. One cannot write tiny,
13500 super-efficient programs using BEINGS, any more naturally than one
13600 can generate efficient machine code using a high level language. By
13700 relinquishing more and more control to the computer language
13800 environment, the programmer sacrifices specialization of the final
13900 code for ease of constructing it and for its greater size and
14000 complexity.
00100 .NEXT PAGE
00200 ⊗28. ACKNOWLEDGEMENTS⊗*
00300
00400 There are, of course, countless ideas embodied in any
00500 concrete project. Sweeping philosophical assumptions are made simply
00600 in trying to do Automatic Programming [McCarthy]. Any
00700 Program-Understanding Program should include the best parts of all
00800 the best old ideas. PUP6 relies on concepts gleaned from Actors
00900 [Hewitt], Demons [Charniak], heterarchy [Reddy], structured
01000 programming [Dijkstra], assertional data bases and flexible data
01100 types [Reboh], pattern-directed invocation of procedural knowledge
01200 [Winograd], the paradigm of dialogue [Floyd], and studies on program
01300 specification techniques [Green]. Of course this list is
01400 incomplete; sophisticated ideas are captured in the languages
01500 themselves: QLISP [Reboh], INTERLISP [Teitelman], LISP [McCarthy2],
01600 and English [Anonymous]. To this rich store, one may achieve new
01700 heights merely by synergy.
01800 The success of the BEINGS project, as well as the precursor
01900 PUP programs [Green] is due in large measure to the encouragement,
02000 advice, support, and creative energy of C. Cordell Green. I have
02100 also drawn upon discussions with the SAIL Automatic Programming
02200 Group, and in particular with D. Barstow, B. McCune, D. Shaw, L.
02300 Steinberg, and R. Waldinger. The generosity of SRI, in providing
02400 computer time and language consultations, should not go unmentioned.